\subsubsection{Übung (iv) - \buchmann{15.5.4}}
\paragraph{Aufgabe}
Modifizieren Sie das Verfahren aus Übung 15.5.3 so, dass seine Sicherheit auf der Schwierigkeit beruht, diskrete Logarithmen zu berechnen.

\paragraph{Lösung}
Alice benutzt einen Primzahl $p$ und eine Primitivwurzel $g\mod{p}$. Sie wählt $a_1,\dotsc,a_k$ gleichverteilt zufällig aus $\{0,1,\dotsc,p-2\}$ und berechnet $A_i=g^{a_i}\mod{p},1\leq i\leq k$.
Der öffentliche Schlüssel ist $(p,g,A_1,\dotsc,A_k)$, der geheime private Schlüssel von Alice ist der Vektor $(a_1,\dotsc,a_k)$

Eine Runde des Zero-Knowledge-Beweises sieht wie folgt aus:

\begin{enumerate}
\item \textbf{Commitment} Der Beweiser Alice wählt zufällig und gleichverteilt einen Exponenten $b\in \{0,1,\dotsc,p-2\}$. Sie berechnet $B\equiv g^b\mod{p}$ und schickt $B$ an den Verifizierer Bob
\item \textbf{Challenge} Bob wählt zufällig und gleichverteilt $(e_1,\dotsc,e_k)\in \{0,1\}^k$ und sendet diesen Vektor an Alice.
\item \textbf{Response} Alice berechnet $y=b+(e_1a_1+\dotsc+e_ka_k)\mod{p-1}$ und sendet es zur Identifikation an Bob.
\item Bob verifiziert, dass $g^y\equiv B\prod_{i=1}^k A_i^{e_i}\mod{p}$ und bestätigt somit Alice' Identität.
\end{enumerate}

Es handelt sich um einen Zero-Knowledge-Beweis:

Würde ein Betrüger versuchen, sich zu Identifizieren, ohne Kenntnis vom geheimen Schlüssel $(a_1,\dotsc,a_k)$ zu haben, müsste er $B$ aus einem festen $y$ berechnen: $$g^y\equiv B\prod_{i=1}^k A_i^{e_i}\mod{p}$$ $$g^y\prod_{i=1}^k A_i^{-e_i}\equiv B\mod{p}$$
Ein Betrüger kann also nur für einen Vektor $(e_1,\dotsc,e_k)$ die Lösung kennen. Die Wahrscheinlichkeit, dass der Verifizierer als Challenge den Vektor $(e_1,\dotsc,e_k)$ des Betrügers wählt, ist $(\frac{1}{2})^k=2^{-k}$.

Die Vollständigkeit und Korrektheit des Protokolls ist damit gegeben.

Das Protokoll kann auch simuliert werden. Man wählt zufällig gleichverteilt $y \in \{0,1,\dotsc,p-2\},(e_1,\dotsc,e_k)\in \{0,1\}^k$. Nun setzt man $B = g^y\prod_{i=1}^k A_i^{-e_i}\mod{p}$. Das Protokoll wird hiermit funktionieren und auch die Wahrscheinlichkeitsverteilung der Protokollnachrichten ist dieselbe wie beim Originalprotokoll.